Biểu diễn chương trình

Theo truyền thống, các chương trình tiến hóa bằng GP được biểu diễn trong bộ nhớ dưới dạng cấu trúc cây.[29] Cấu trúc cây có thể được định lượng dễ dàng một cách đệ quy. Mọi nút cây đều có một toán tử hàm và mọi nút đầu cuối đều có một toán hạng, làm cho việc tiến hóa và định lượng các biểu thức toán học trở nên dễ dàng. Vì vậy, theo truyền thống GP ủng hộ việc sử dụng các ngôn ngữ lập trình có cấu trúc cây một cách tự nhiên (ví dụ: Lisp, các ngôn ngữ lập trình hàm khác cũng phù hợp).

Các biểu diễn không phải cây đã được đề xuất và thực hiện thành công, chẳng hạn như lập trình di truyền tuyến tính phù hợp với các ngôn ngữ mệnh lệnh vốn truyền thống hơn [ví dụ, xem Banzhaf et al. (1998)].[30] Phần mềm GP thương mại Discipulus sử dụng mã máy nhị phân đệ quy tự động ("AIM")[31] để đạt được hiệu suất tốt hơn. µGP[32] sử dụng đa đồ thị có hướng để tạo ra các chương trình khai thác triệt để cú pháp của một hợp ngữ nhất định. Các biểu diễn chương trình khác mà các công trình nghiên cứu và phát triển quan trọng đã thực hiện bao gồm các chương trình cho máy ảo dựa trên ngăn xếp,[33][34][35] và chuỗi các số nguyên được ánh xạ tới các ngôn ngữ lập trình tùy ý thông qua ngữ pháp.[36][37] Lập trình di truyền Descartes là một dạng khác của GP sử dụng biểu diễn đồ thị thay vì biểu diễn dựa trên cây thông thường để mã hóa các chương trình máy tính.

Hầu hết các biểu diễn chứa phần mã vô hiệu về mặt cấu trúc (intron). Các gen không mã hóa như vậy có vẻ vô dụng vì chúng không ảnh hưởng đến hoạt động của bất kỳ cá thể nào. Tuy vậy, chúng thay đổi xác suất tạo ra các con khác nhau dưới các toán tử biến dị, và do đó làm thay đổi các thuộc tính biến dị của cá thể. Các thí nghiệm dường như cho thấy sự hội tụ nhanh hơn khi sử dụng các biểu diễn chương trình cho phép các gen không mã hóa so với các biểu diễn chương trình không có bất kỳ gen không mã hóa nào.[38][39]

Chọn lọc

Chọn lọc là một quá trình theo đó những cá nhân nhất định được chọn từ thế hệ hiện tại sẽ đóng vai trò là cha mẹ cho thế hệ tiếp theo. Các cá nhân được chọn theo xác suất để những cá nhân có thành tích tốt hơn có cơ hội được chọn cao hơn.[18] Phương pháp chọn lọc phổ biến nhất được sử dụng trong GP là chọn lọc giải đấu, mặc dù các phương pháp khác như chọn lọc thích nghi tỉ lệ, chọn lọc lexicase,[40] và các phương pháp khác đã được chứng minh là hoạt động tốt hơn đối với nhiều vấn đề về GP.

Chọn lọc tinh hoa, hay gieo mầm cho thế hệ tiếp theo với cá thể tốt nhất (hoặc n cá thể tốt nhất) từ thế hệ hiện tại, là một kỹ thuật đôi khi được sử dụng để tránh thoái triển.

Trao đổi chéo

Trong Lập trình di truyền, hai cá thể phù hợp được chọn từ quần thể để làm bố mẹ cho một hoặc hai con. Trong lập trình di truyền cây, những bậc cha mẹ này được biểu diễn dưới dạng cây treo ngược, với các nút gốc ở trên cùng. Trong trao đổi chéo cây con, ở mỗi cá thể cha mẹ, một cây con (subtree) được chọn ngẫu nhiên. (Được đánh dấu bằng màu vàng trong hoạt hình.) Bên trong cá thể cha mẹ hiến gốc (trong hoạt hình bên trái), cây con đã chọn sẽ bị xóa và được thay thế bằng một bản sao của cây con được chọn ngẫu nhiên từ cá thể cha mẹ còn lại, để tạo ra một cá thể con mới (child tree).

Đôi khi trao đổi chéo hai con được sử dụng, trong trường hợp đó, cây con đã bị xóa (trong hoạt hình bên trái) không chỉ bị xóa mà được sao chép vào bản sao của cá thể cha mẹ thứ hai (ở đây bên phải) thay thế (trong bản sao) cây con đã được chọn ngẫu nhiên trước đó. Do đó, kiểu trao đổi chéo cây con này lấy hai cá thể thích nghi và tạo ra hai cá thể con.

Đột biến

Có nhiều dạng đột biến trong lập trình di truyền. Chúng đều xuất phát từ một cá thể cha mẹ thích nghi và đúng về mặt cú pháp và nhắm đến mục tiêu tạo ra một cá thể con ngẫu nhiên đúng về mặt cú pháp. Trong hoạt ảnh, một cây con được chọn ngẫu nhiên (được đánh dấu bằng màu vàng). Nó bị loại bỏ và thay thế bằng một cây con được tạo ngẫu nhiên.

Các phép đột biến khác chọn một lá (nút bên ngoài) của cây và thay thế nó bằng một lá được chọn ngẫu nhiên. Một phép đột biến khác nữa là chọn ngẫu nhiên một hàm (nút bên trong) và thay thế nó bằng một hàm khác có cùng arity (số đối số). Phép đột biến dịch lên chọn ngẫu nhiên một cây con và thay thế nó bằng một cây con bên trong chính nó. Do đó đột biến dịch lên bảo đảm con có kích thước nhỏ hơn. Phép thay thế lá và thay thế hàm cùng số đối số đảm bảo con có cùng kích thước với cha mẹ. Trong khi đó, đột biến cây con (trong hoạt hình) có thể, tùy thuộc vào tập hợp các hàm và đầu cuối, có xu hướng làm tăng hoặc giảm kích thước cây. Các đột biến dựa trên cây con khác cố gắng kiểm soát cẩn thận kích thước của cây con thay thế và do đó kích thước của cá thể con

Tương tự, có nhiều dạng đột biến lập trình di truyền tuyến tính, mỗi dạng đều cố gắng đảm bảo cá thể con bị đột biến vẫn đúng về mặt cú pháp.